Dual Problem

In the solution of linear programming, there are times when the solution is not unique, or degenerate solution. Multi-solutions correspond to infinite solutions, while degenerate solution corresponds to  basic variables which equal to 0. It seemly that there bears no relation between them. However, derived from the iterations of simplex table, the column of b and the row of test number represent a basic solution of the primal problem and the dual problem respectively.

     If the primal problem has multi-solutions, then:
    (1) all the test numbers are less than or equal to 0, while one of non-basic variables equals to 0.
     (2) one of the basic variables in the basic solution of the dual problem equals to 0, that is to say: a degenerated optimal solution.

    Based on the analysis aforementioned, a conclusion can be reasonably drawn that : If the primal problem has multi-solutions, then its dual problem has a degenerated optimal solution; If the dual problem has multi-solutions, then the primal problem has a degenerated optimal solution.